'''

Created on May 12, 2010

@author: roni
'''
import groupUtils
import logging
from ns2Scenario import Ns2Scenario
from gde import GDE

class MinimalCardinalityGde(GDE):
    '''
    MBD algorithm for finding the delayed links
    '''
    def __init__(self,activate_prunning = True):
        GDE.__init__(self,activate_prunning)
        self.name = "%s-MinCard" % self.name        
        self.max_diagnoses = float('inf')
    
    def run(self,scenario, observed_details,delay_steps=Ns2Scenario.LINK_DELAY):
        ''' Run the diagnosis 
        param - scenario - a Ns2Scenario object described the model
        param - observed - a map of agent to delay, describing the actual delay seen'''
        self.min_cardinality = float('inf')
        GDE.run(self,scenario,observed_details,delay_steps)
    
    
    def diagnose(self,conflict_agents, possible_abnormal_nodes, abnormal_nodes = set()):
        ''' Returns a generator function that generates diagnosises 
        param conflict_agents - agents that still have an unexplained conflict 
        param possible_abnormal_nodes - nodes that may be abnormal, which may explain conflict of agents
        param abnormal_nodes - nodes that are assumed to be abnormals (satisfied previous agents)'''
        
        # Limit the number of diagnoses to make runtime relevant
        if len(self.diagnosises)>self.max_diagnoses:
            return
        
        # If all agents are satisfied - a diagnosis has been found
        if len(conflict_agents)==0:
            cardinality = len(abnormal_nodes)
            if self.min_cardinality>cardinality:
                self.min_cardinality = cardinality
                self.diagnosises=[abnormal_nodes] # Remove old diagnoses that were not minimal cardinality            
                logging.info("Found smaller diagnosis %d %s" % (len(abnormal_nodes),abnormal_nodes))
            return 
        
        agent = self.pop_agent(conflict_agents)
        all_sat_sets = self.find_all_sat_sets(agent, possible_abnormal_nodes,abnormal_nodes)        
        
        # If it is possible to satisfy the agent
        if len(all_sat_sets)!=0:
            # Go over all of the possible explanations that satisfy the selected agent
            while len(all_sat_sets)>0:
                # Choose possible satsifying nodes for agent
                sat_abnormal_nodes = self.pop_sat_set(all_sat_sets)

                # New abnormal contains the old abnormals and the new satisfying set
                new_abnormal_nodes = abnormal_nodes.union(sat_abnormal_nodes)

                # New possible abnormals must not contain normal nodes on agent's path                
                new_no_conflict_nodes = self.find_no_conflict_nodes(agent, new_abnormal_nodes)
                new_possible_abnormals = possible_abnormal_nodes.difference(sat_abnormal_nodes)
                new_possible_abnormals.difference_update(new_no_conflict_nodes)
                
                # Search for diagnosis that will satisfy the remaining conflicted agents
                self.diagnose(conflict_agents,new_possible_abnormals, new_abnormal_nodes)
        
        # Add this agent back to the agent list, to consider it in next iterations
        conflict_agents.add(agent)
                        
   
    def find_all_sat_sets(self,agent, possible_abnormal_nodes,abnormal_nodes):
        ''' Find all possible sets of abnormal nodes that satisfy the given agent conflict 
            A list containing an empty list means that there is no conflict (perhaps satisfied due to the nodes already in abnormal_nodes
            An empty list means that it is not possible to satisfy the agent's conflict with the given possible_abnormal_nodes 
        '''
        nodes_on_path = self.agent_to_nodes_on_path[agent]
        
        # Remove the nodes that have already been set as abnormal        
        unexplained_delay = self.unexplained[agent]
        abnormals_on_path = nodes_on_path.intersection(abnormal_nodes)
        unexplained_delay = unexplained_delay-len(abnormals_on_path)*2
        
        # If too much abnormals for delay - current diagnosis is not consistent
        if (unexplained_delay<0):
            return []
        
        # If all the observed delay has been explained
        if (unexplained_delay==0):
            return [[]]
        
        possible_abnormals_on_path = nodes_on_path.intersection(possible_abnormal_nodes)        
        # If possible abnormals on path cannot explain delay - not sat set exists
        if (len(possible_abnormal_nodes)<unexplained_delay/2):
            return []

        # Pruning to find minimum cardinality diagnosis
        if self.min_cardinality<=unexplained_delay/2+len(abnormal_nodes):
            return []
       
        
        # Generate the n choose k possible subsets of possible_abnormals_on_path
        return groupUtils.all_subsets_of_size(unexplained_delay/2, possible_abnormals_on_path)
        
  
        
        